package offerbook.Code25_pathInBT;

import utils.TreeNode;
import utils.TreeUtil;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 输出二叉树从根节点开始的所有路径,
 * 注：路径满足以任意开始，以任意结束。 满足从上到下即可
 * @date 2020/3/9 18:48
 */
public class Code03_FindAllPath3 {
    public static List<List<Integer>> findAllPath(TreeNode treeNode) {
        List<List<Integer>> totalPath = new ArrayList<>();
        if (treeNode == null) {
            return totalPath;
        }
        List<Integer> path = new LinkedList<>();
        preInOder(treeNode, totalPath,path);
        return totalPath;
    }

    private static void preInOder(TreeNode root, List<List<Integer>> totalPath, List<Integer>
            path) {
        if(root == null) return;
        //前序遍历要处理的当前节点,先添加当前节点
        path.add(root.val);

        //以当前节点为路径重点，开始添加。前面所有节点开始遍历到当前节点
        for (int i = 0; i < path.size(); i++) {
            totalPath.add(new LinkedList<>(path.subList(i,path.size())));
        }

        preInOder(root.left, totalPath, path);
        preInOder(root.right, totalPath, path);

        //返回上一级，要删除当前节点
        path.remove(path.size() - 1);
    }
    public static void main(String[] args) {
        TreeNode root = new TreeNode(10);
        root.left = new TreeNode(5);
        root.right = new TreeNode(12);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(7);
        TreeUtil.printTree(root);
        List<List<Integer>> totalPath = findAllPath(root);
        System.out.println(totalPath);
    }
}
